Modular multiplication is extensively used in implementing cryptographic methods such as RSA cryptography.
The Montgomery algorithm is one of the most efficient techniques for performing modular multiplication. Its use is particularly effective where high performance is required so as to minimise the computation time.
The Montgomery proof is given in Appendix 1 and the Montgomery Reduction Algorithm is outlined below:
Montaomery Algorithm To enact the P operator on A.B we follow the process outlined below:
(1) X=A.B+S {S initially zero} PA1 (2) Y=(X.J) mod2.sup.n (where J is a pre-calculated constant) PA1 (3) Z=X+Y.N PA1 (4) S=Z/2.sup.n PA1 (5) P=S (modN) (N is subtracted from S, if S.gtoreq.N) PA1 Thus P P(A.B).sub.N (the result in the Montgomery Field of numbers)
In financial applications where smartcards are used as a means of ensuring a high level of security during the transaction, Public Key Cryptography is becoming increasingly popular. Public Key Cryptography offers a higher level of protection than the traditional symmetric or private key methods but until recently has been expensive to implement. Advances in technology have now made the implementation of such methods cost effective. RSA Public Key capability has been designed into smartcard microcontrollers which also include an on-chip co-processor which has been specifically designed to perform modular multiplications for operands each of 512 bit length. The co-processor is directly driven by the microcontroller's CPU under software control by a program stored either in ROM or in EEPROM. Such a co-processor which implements the Montgomery algorithm for modular reduction without the division process and is known from European Patent Publication EP-0601907-A.
As will be discussed in detail hereafter, such a known co-processor suffers from a number of disadvantages.